package _05_二叉树;

import java.util.ArrayList;
import java.util.List;

public class _剑指Offer_34二叉树中和为某一值的路径 {

    private List<List<Integer>> results = new ArrayList<>();

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        if (root == null) return results;
        findTarget(root, target, new ArrayList<>());
        return results;
    }

    public void findTarget(TreeNode root, int target, List<Integer> list) {
        target -= root.val;
        // 左子树
        list.add(root.val);
        if (root.left == null && root.right == null && target == 0) {
            results.add(new ArrayList<>(list));
        }
        if (root.left != null) {
            findTarget(root.left, target, list);
        }
        if (root.right != null) {
            findTarget(root.right, target, list);
        }

        list.remove(list.size() - 1);
    }

}
